A current challenge for network equipment and network service suppliers is testing and evaluating products under realistic network volume and conditions. Packet processing requires a priori knowledge of a current state of a connection associated with the packet to be processed. When processing protocol exchange packets, therefore, the packet header field provides information that is used to retrieve state information from memory. During operation, the devices that are tested maintain and process information for millions of connections. Therefore, realistic header fields are large. A look up function that uses a large number of bits to perform the addressing is complex and time-consuming and can potentially be a limiting factor in packet processing. It is important, therefore, to perform the retrieval step as efficiently as possible.
Prior art approaches to the retrieval step include a hardware implementation using content addressable memory (herein “CAM”). The hardware implementation using CAM is fast, but can be very expensive for a large number of connections. Additionally, CAM consumes significant printed circuit board real estate, which is also costly. Another prior art approach is a software implementation using sort algorithms. The software implementation is optimized for the specific sort involved, but is relatively slow and can be a limiting factor in the rate of packets processed. A hybrid implementation is also known involving a number of CAMs to create a hardware assisted search, however hybrid systems are expensive to implement on a large scale.
There remains a need, therefore, for efficient process and apparatus to perform the look up function of state information based upon packet header information.